Covalent modifications of histones, such as acetylation and methylation, play important roles in the regulation of gene expression. Histone lysine methylation has been implicated in both gene activation and repression, depending upon the specific lysine (K) residue that becomes methylated and the state of methylation (mono-, di- or trimethylation). Methylation on K4, K9 and K36 of histone H3 has been shown to be reversible and can be removed by site-specific demethylases. However, the enzymes that antagonize methylation on K27 of histone H3 (H3K27), an epigenetic mark important for embryonic stem cell maintenance, Polycomb-mediated gene silencing and X chromosome inactivation, have been elusive. Here we show the JmjC domain-containing protein UTX, as well as the related JMJD3, specifically removes methyl marks on H3K27 in vitro. Further, the demethylase activity of UTX requires a catalytically active JmjC domain. Finally, overexpression of UTX and JMJD3 leads to reduced di- and trimethylation on H3K27 in cells, suggesting that UTX and JMJD3 may function as H3K27 demethylases in vivo. The identification of UTX and JMJD3 as H3K27-specific demethylases provides direct evidence to indicate that similar to methylation on K4, K9 and K36 of histone H3, methylation on H3K27 is also reversible and can be dynamically regulated by site-specific histone methyltransferases and demethylases.